#include<stdio.h>
#include<string.h>
/*
 *归并排序：
 *1.分治
 *2.将两已排好序的数组进行合并
 *
 *before data array: 1 5 7 8 3 5 9 4 1 0 
 *after data array: 0 1 1 3 4 5 5 7 8 9
 */

void mergesort(int * data, int start, int end);
void sort(int * data, int left, int mid, int right);
int main(){
	int data[] = {1, 5, 7, 8, 3, 5, 9, 4, 1, 0};
	int i = 0;
	int length = sizeof(data) / sizeof(int);
	printf("before data array: ");
	for(i = 0; i < length; i++){
		printf("%d ", data[i]);
	}
	mergesort(data, 0, length - 1);
	
	printf("\nafter data array: ");
	for(i = 0; i < length; i++){
		printf("%d ", data[i]);
	}
}

void mergesort(int * data, int start, int end){
	if(start < end){
		int mid = (start + end) / 2;
		mergesort(data, start, mid);
		mergesort(data, mid+1, end);
		sort(data, start, mid, end);
	}
}

void sort(int * data, int left, int mid,  int right){
	int length = right - left + 1;
	int tmp[length];
	memset(tmp, 0, sizeof(tmp));

	int start1 = left;
	int end1 = mid;
	int start2 = mid+1;
	int end2 = right;
	int i = 0;

	while(start1 <= end1 && start2 <= end2){
		if(data[start1] <= data[start2]){
			tmp[i++] = data[start1++];
		}else{
			tmp[i++] = data[start2++];
		}
	}

	while(start1 <= end1){
		tmp[i++] = data[start1++];
	}
	while(start2 <= end2){
		tmp[i++] = data[start2++];
	}

	//将排好序的tmp数组复制给data数组
	for(int j = 0; j < length; j++){
		data[left++] = tmp[j];
	}
}
